1
Foundations of Combinatorial Logic
MATH002 Lesson 11
00:00
Imagine a system where the present is all that matters—no memory of the past, no anticipation of the future. This is the world of combinatorial logic. Here, digital circuits act as instant mathematical translators, turning a specific combination of input signals into a unique output without the complexity of feedback loops or internal storage. It is the purest physical manifestation of Boolean algebra.

The Recursive Architecture of Logic

To build complex digital brains, we must first define the grammar of their language. In any Boolean algebra $(S, +, \cdot, ', 0, 1)$, we define Boolean expressions over a set of variables $x_1, \dots, x_n$ through a process of structural induction:

The Base Case

1. Every constant $s \in S$ is a Boolean expression.
2. Every variable $x_1, \dots, x_n$ is a Boolean expression.

The Recursive Step

If $X_1$ and $X_2$ are already Boolean expressions, then the following are also valid expressions:

$(X_1), \quad X_1', \quad X_1 + X_2, \quad X_1 \cdot X_2$

Precedence and Efficiency

In the absence of parentheses, we follow a strict hierarchy to avoid ambiguity: Conjunction ($\\land$) always takes precedence over Disjunction ($\\lor$). Furthermore, to optimize hardware design, we utilize $n$-input gates. Instead of chaining multiple 2-input gates, we represent $a_1 \vee a_2 \vee \dots \vee a_n$ as a single logical unit, reducing propagation delay and simplifying the circuit topology.

The Structural Mapping Principle

Every algebraic expression is a blueprint for a physical circuit. Consider the construction for $(x_1 \wedge (\neg x_2 \vee x_3)) \vee x_2$:

  • Inner Layer: We first isolate $(\neg x_2 \vee x_3)$ using a NOT gate and an OR gate.
  • Middle Layer: The result is fed into an AND gate alongside the signal from $x_1$.
  • Outer Layer: Finally, the AND output and the original $x_2$ line meet at a terminal OR gate.
🎯 Core Principle
A combinatorial circuit's topology is a direct physical reflection of its Boolean expression's order of operations. No memory, no feedback—just pure, instantaneous mapping.